#ifndef GRAPH_H
#define GRAPH_H

#include "minqueue.h"
#include "additional_structs_graph.h"
#include "queue.h"

#define DEBUG_G       // calculation of relaxations and stuff

//#define COPY_COUNTS 		10

/// <class Graph used to incapsulate operations with graphs and its contents
class Graph
{
public:
    // constructors:
    Graph();
    Graph(const Knots* structure, int n);
    void InitWithData(const Knots* structure, int n);
    void ReInitWithoutDeletion(Knots* structure, int n);
    // calculation of ways
    void applyBellmanFord(); ///! Calculates distances with Bellman-Ford algorithm
    void applyDejkstra();///! Calculates distances with Dejkstra algorithm
    void applyCyclon(); ///! Another modification... 
    void setStart(int n);   ///! Sets starting point in the graph
    void setInfoAboutLineNums(int* line_nums);
    void applyCyclonC(int* allowedLineNumbers, int nAllowedCount);

    void applyCyclonB();

    // getting info-methods:
    int getWeight(int node);

    /*
    int* getNextCopyOfParents();
    int* getPrevCopyOfParents();
    //void applyCyclonC(int *allowedNumbersOflines);//calculates the weights only for 
    //given numbers of lines;

    */
    bool areWeAtTheStartOrEnd();
    void deleteAllParentsHistory();

    virtual ~Graph();
     // constants
    enum{
        Infinity=999999999,     ///! a constant for infinity (sorting)
        Nill = -1,               ///! a nil-pointer
    };

    int getParent(int node);
    void printParents();
    void printWeights();

protected:
    void commonInit();
    void distancesInit();
    // 2.04.2009 I'll save memory I will not use such methods:
    //void makeACopyOfParents();
    // a pointer for copied parents, there we are...
    int _nCurPointerToParent;
    int* _anLinesOfNodes;
    void relax(int u, int v, int weight); ///! Calculates new weight of knot, if its way shorter than it was before... for the pair of nodes u, v
    MinQueue queue; ///! Queue for Dejkstra algorithm
    Queue* _anNumbersNextToUse;
    Queue* _anNumbersOfLinesUsed;
    Queue* _anCurLineNodeNumbers;///! Nodes which we want to see next time;
    Queue* _knotsWhereIveBeen; ///! Knots Numbers, where I've already been in the current line
    int 	_nLastLength;
    Knots* _Knots;
    int _nStart; ///! Start position of the graph
    int _nLength; ///! The length of the graph
    int* _afD; ///! Containts distances from source root to the distanation
    int* _anParent; ///! Parents' history (the way from s to all other knots);
    //int** _aanParent; ///! Copy of other ways to the destination...
    int _nOtherWaysCount; ///! Amount of the other ways we can go the destination
};

#endif // GRAPH_H
